package com.ice.core.utils;

/**
 * @author zjn
 * Ice的linkedList
 * 与jdk LinkedList区别:不断链
 * 被删除的节点的next和prev不断链
 * 保证操作链表时不会中断操作前的执行
 */
public final class IceLinkedList<E> {

/*
   * Pointer to first node.
   * Invariant: (first == null && last == null) ||
   * (first.prev == null && first.item != null)
   */
  private Node<E> first;

/*
   * Pointer to last node.
   * Invariant: (first == null && last == null) ||
   * (last.next == null && last.item != null)
   */
  private Node<E> last;

  private int size;

  public boolean isEmpty() {
    return this.size == 0;
  }

  public int getSize() {
    return size;
  }

  public Node<E> getFirst() {
    return first;
  }

  public boolean add(E e) {
    linkLast(e);
    return true;
  }

  @SafeVarargs
  public final boolean addAll(E... es) {
    for (E e : es) {
      linkLast(e);
    }
    return true;
  }

  public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
  }

  private void checkElementIndex(int index) {
    if (!isElementIndex(index)) {
      throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
    }
  }

  Node<E> node(int index) {

    if (index < (size >> 1)) {
      Node<E> x = first;
      for (int i = 0; i < index; i++) {
        x = x.next;
      }
      return x;
    } else {
      Node<E> x = last;
      for (int i = size - 1; i > index; i--) {
        x = x.prev;
      }
      return x;
    }
  }

/*
   * Tells if the argument is the index of an existing element.
   */
  private boolean isElementIndex(int index) {
    return index >= 0 && index < size;
  }

/*
   * Links e as last element.
   */
  void linkLast(E e) {
    final Node<E> la = last;
    final Node<E> newNode = new Node<>(la, e, null);
    last = newNode;
    if (la == null) {
      first = newNode;
    } else {
      la.next = newNode;
    }
    size++;
  }

  public boolean remove(Object o) {
    if (o == null) {
      for (Node<E> x = first; x != null; x = x.next) {
        if (x.item == null) {
          unlink(x);
          return true;
        }
      }
    } else {
      for (Node<E> x = first; x != null; x = x.next) {
        if (o.equals(x.item)) {
          unlink(x);
          return true;
        }
      }
    }
    return false;
  }

/*
   * Unlinks non-null node x.
   */
  E unlink(Node<E> x) {
    // assert x != null;
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;

    if (prev == null) {
      first = next;
    } else {
      prev.next = next;
    }

    if (next == null) {
      last = prev;
    } else {
      next.prev = prev;
    }

    size--;
    return element;
  }

  public static class Node<E> {
    public E item;
    public Node<E> next;
    public Node<E> prev;

    public Node(Node<E> prev, E element, Node<E> next) {
      this.item = element;
      this.next = next;
      this.prev = prev;
    }
  }
}
